In many science and engineering computational problems, it is desirable to outsource the computation to an external computing agent in such a way that the customer's information is hidden from the external agent, and yet the answers returned by the agent can be used to obtain easily the true answer. The computations required to be performed on a local computer are proportional to the size of the local input, which is unavoidable. The bulk of the computational task falls on the external agent, which would typically be an entity with considerable computing power, such as a supercomputing center. It is desirable to find a way to improve these outsourcing techniques, and, in particular, to enable multiple parties to contribute information to the outsourced computation.
Rapid growth in the area of computer technology, including networking schemes like the Internet, has facilitated the transmission of data from a processing system at one site (the customer) to another site (the agent) to perform certain computations. Such “outsourcing” of certain computations may be desired, for example, when the customer lacks the hardware resources, software resources, or other know-how to cost-effectively perform the computations.
In one example, outsourcing is utilized in the financial services industry, where, for instance, the customer data includes projections of the likely future evolution of certain commodity prices, interest and inflation rates, economic statistics, portfolio holdings, etc. In another example, outsourcing is utilized in the energy services industry, where the proprietary data is typically seismic, and can be used to estimate the likelihood of finding oil or gas at a particular geographic spot in question. The seismic data may be so massive that the performance of corresponding matrix multiplication and inversion computations would be beyond the resources of most major oil companies. Many other industries can also benefit from outsourcing.
With the advent of computational outsourcing, concerns regarding the agent's misappropriation of customer data or the computational results have arisen. These concerns arise not only with the customer, but also with an agent who wants to reduce the risk of misappropriation by its employees. One proposed technique is to utilize standard cryptographic techniques to encrypt the data sent by the customer to the agent. While encryption may enhance security with respect to an attacking third party, it still requires that the agent have access to at least some of the cryptographic information, such as encryption/decryption keys, to perform a meaningful calculation. As a result, this technique still provides the agent ready access to the actual data. Moreover, such techniques assume the agent will be a permanent repository of the data, performing certain operations on it and maintaining certain predicates. In many instances, this situation also is undesirable.
For the foregoing reasons, there is a need for techniques enabling a customer to securely outsource computations to an agent. The desired techniques should reduce the risk of misappropriation by an agent or an agent's employee of a customer's data sent to an agent for an outsourced computation. Preferably, the desired techniques should enable a customer to disguise its data before disclosing it to an agent, without the need for encryption of the customer's data.